package datastructure;

/**
 * Created with IntelliJ IDEA.
 * Description:
 *
 * @author lzy
 * @create 2019-11-12 上午10:14
 */
public class ArrayListCircleTest {
    /**
     * 判断链表是否成环
     *
     * @param head
     * @return
     */
    public static boolean isCycle(Node head) {
        Node p1 = head;
        Node p2 = head;
        // 移动p1和p2
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                return true;
            }
        }

        return false;
    }

    /**
     * 计算环的长度
     *
     * @param head
     * @return
     */
    public static int calculateCycleLength(Node head) {
        Node p1 = head;
        Node p2 = head;
        int p1Step = 0;
        int p2Step = 0;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            p1Step++;
            p2Step += 2;
            if (p1 == p2) {
                return p2Step - p1Step;
            }
        }
        return 0;
    }

    /**
     * 计算入环点的位置
     *
     * @param head
     * @return
     */
    public static Node calculateCycleIndex(Node head) {
        Node p1 = head;
        Node p2 = head;
        // 移动p1和p2
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            // 先找出首次相遇点，将p2放回到开始点，然后每次移动一步，再次相遇的地点就是入环点
            if (p1 == p2) {
                p2 = head;
                int index = 0;
                while (p1 != p2) {
                    p1 = p1.next;
                    p2 = p2.next;
                    index++;
                }
                Node result = head;
                for (int i = 0; i < index; i++) {
                    result = result.next;
                }
                return result;
            }
        }

        return null;
    }

    public static void main(String[] args) {
        Node node1 = new Node(5);
        Node node2 = new Node(3);
        Node node3 = new Node(7);
        Node node4 = new Node(2);
        Node node5 = new Node(6);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node2;

        System.out.println(isCycle(node1));
        System.out.println(calculateCycleLength(node1));
        System.out.println(calculateCycleIndex(node1));
    }

    /**
     * 链表节点
     */
    private static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data + "}";
        }
    }
}
